\contentsline {section}{\numberline {1}研究背景}{3}
\contentsline {section}{\numberline {2}图划分算法}{3}
\contentsline {subsection}{\numberline {2.1}随机划分}{4}
\contentsline {subsubsection}{\numberline {2.1.1}哈希划分算法流程}{4}
\contentsline {subsection}{\numberline {2.2}谱方法}{4}
\contentsline {subsubsection}{\numberline {2.2.1}谱聚类算法流程}{5}
\contentsline {subsection}{\numberline {2.3}启发式算法}{5}
\contentsline {subsubsection}{\numberline {2.3.1}Kernighan-Lin算法流程}{5}
\contentsline {subsection}{\numberline {2.4}多层划分算法}{7}
\contentsline {subsubsection}{\numberline {2.4.1}Metis算法流程}{7}
\contentsline {subsubsection}{\numberline {2.4.2}粗化阶段}{7}
\contentsline {paragraph}{随机策略}{9}
\contentsline {paragraph}{权重边策略}{9}
\contentsline {subsubsection}{\numberline {2.4.3}初始划分阶段}{9}
\contentsline {subsubsection}{\numberline {2.4.4}细化阶段}{10}
\contentsline {section}{\numberline {3}基于Spark的图划分}{10}
\contentsline {subsection}{\numberline {3.1}图数据实现}{10}
\contentsline {subsubsection}{\numberline {3.1.1}\texttt {Node}类}{10}
\contentsline {subsubsection}{\numberline {3.1.2}\texttt {Graph}类}{10}
\contentsline {subsection}{\numberline {3.2}哈希划分算法实现}{12}
\contentsline {subsection}{\numberline {3.3}谱聚类算法实现}{12}
\contentsline {subsection}{\numberline {3.4}Kernighan-Lin算法实现}{13}
\contentsline {subsection}{\numberline {3.5}Metis算法实现}{13}
\contentsline {section}{\numberline {4}总结}{16}
